package com.demo78_子集2;

import java.util.*;

/**
 * 我去  这种方法直接少了这么多 ,  那个还要3000多次, 这个直接只要1000多次
 *
 */
public class Solution {
    public static int time;

    public static void main(String[] args) {
        int[] ints = {1,2,3,4};
        List<List<Integer>> subsets = subsets(ints);
        System.out.println(time);
    }
    public static List<List<Integer>> subsets(int[] nums) {

        List list = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> empty = new ArrayList<>();
        list.add(empty);
        if (nums.length==0){
            return list;
        }
        ArrayList<Integer> path = new ArrayList<>();
        dfs(0,nums,path,list);
        return list;
    }

    private static void dfs(int startIndex, int[] nums, ArrayList<Integer> path, List list) {
        // 边界条件, 到最后一个元素了
        if (startIndex==nums.length){
            return;
        }

        /**
         * 这里最开始是从1开始的元素, 很容易理解, 但是如何又切换到 2开始的呢?   比如:  1 , 1 2 , 1 2 3 ,....   那如何跳到2 3 4 , 2 3 呢?
         * 那是在添加完第一个元素后, 直到递归完所有的,  便开始把最开始添加的这个 1 给剔除掉了.  remove() 掉了.  此时集合中元素个数为0
         * 那么下一次再添加就是这个添加的是元素2了~
         */
        // 单层搜索的逻辑~
        for (int j = startIndex; j < nums.length; j++) {
            //处理当前结点
            path.add(nums[j]);
            // 收集结果
            ArrayList<Integer> tempList = new ArrayList<>();
            for (Integer item : path) {
                tempList.add(item);
            }
            list.add(tempList);

            time++;
            // 纵向递归
            dfs(j+1,nums,path,list);
            // 回溯
            path.remove(path.size()-1);

        }
    }
}
